package demo3;

import java.util.Arrays;

/**
 * 希尔排序 改进的插入排序 步长
 */
public class ShellSortTest {
    public static void main(String[] args) {
        int[] arr = new int[]{4,2,9,5,1,16,3};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void shellSort(int[] arr) {
        int step = arr.length/2; // 初始步长为数组长度的一半
        while(step>=1){
            for (int i = 0; i < step; i++) {
                for (int j = i+step; j < arr.length; j += step) {
                    int temp = arr[j];
                    int k;
                    for (k = j-step; k >= 0 && temp < arr[k]; k -= step) {
                        arr[k+step] = arr[k];
                    }
                    // 注意因为因为for循环时把计算k时减了step，所有这里需要加回来
                    arr[k+step] = temp;
                }
            }
            step = step/2;
        }
    }
}
